package Math;//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [2,2,3,2]
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：nums = [0,1,0,1,0,1,99]
//输出：99
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 3 * 10⁴ 
// -2³¹ <= nums[i] <= 2³¹ - 1 
// nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 
// 
//
// 
//
// 进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？ 
// Related Topics 位运算 数组 👍 733 👎 0


import java.util.HashSet;

//leetcode submit region begin(Prohibit modification and deletion)
class singleNumberII {
    //求和法会超出int范围,不可行
    public int singleNumber(int[] nums) {
        /**
         * 首先记录数组全部的和sum1，然后记录去重后的和sum2
         * 那么  sum2 - sum1/3 = 唯一数
         * */
        long sum1 = 0;
        long sum2 = 0;
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length ; i++) {
            sum1 += nums[i];
            if(set.add(nums[i])){
                sum2 += nums[i];
            }
        }
        return (int)(3*sum2 - sum1)/2;
    }
    //位数法
    public int singleNumber1(int[] nums) {
        int res = 0;
        /**
         * 数的二进制位每一位相加，然后对其每一位的和取余
         *
         * 如果其他数都出现 3 次，只有目标数出现 1 次，那么每一位的 1 的个数无非有这2种情况，
         * 为 3 的倍数（全为出现三次的数） 或
         * 3 的倍数 +1（包含出现一次的数）。
         * 这个 3 的倍数 +1 的情况也就是我们的目标数的那一位。
         * */
        for (int i = 0; i < 32; i++) {
            int count = 0;
            for (int j = 0; j < nums.length; j++) {
                //先将位数右移，并求出最后一位的为1的个数
                if(((nums[j] >> i) & 1) == 1  ){
                    count++;
                }
            }
            //若和count不是3的倍数,说明这一位是只出现一次的数带来的
            if(count%3 != 0){
                //将该位复位
                res = res | 1 << i;
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
